import java.util.*;

public class BreadthFirstSearchSolution {

    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length, n = maze[0].length;
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{entrance[0], entrance[1], 0});
        maze[entrance[0]][entrance[1]] = '+';

        while (!queue.isEmpty()) {
            int[] point = queue.poll();
            int x = point[0], y = point[1], d = point[2];

            for (int i = 0; i < 4; i++) {
                int newX = x + dx[i], newY = y + dy[i];
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && maze[newX][newY] == '.') {
                    if (newX == 0 || newX == m - 1 || newY == 0 || newY == n - 1) {
                        return d + 1;
                    }
                    queue.offer(new int[]{newX, newY, d + 1});
                    maze[newX][newY] = '+';
                }
            }
        }
        return -1;
    }


    public int shortestBridge(int[][] grid) {
        int n = grid.length;
        Queue<int[]> queue = new LinkedList<>();
        Queue<int[]> isLand = new LinkedList<>();
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    grid[i][j] = -1;

                    while (!queue.isEmpty()) {
                        int[] point = queue.poll();
                        int x = point[0], y = point[1];
                        isLand.offer(point);

                        for (int k = 0; k < 4; k++) {
                            int newX = x + dx[k], newY = y + dy[k];
                            if (newX >= 0 && newX < n && newY >= 0 && newY < n && grid[newX][newY] == 1) {
                                queue.offer(new int[]{newX, newY});
                                grid[newX][newY] = -1;
                            }
                        }
                    }

                    int step = 0;
                    while (!isLand.isEmpty()) {
                        int levelSize = isLand.size();
                        for (int k = 0; k < levelSize; k++) {
                            int[] point = isLand.poll();
                            int x = point[0], y = point[1];

                            for (int m = 0; m < 4; m++) {
                                int newX = x + dx[m], newY = y + dy[m];
                                if (newX >= 0 && newX < n && newY >= 0 && newY < n) {
                                    if (grid[newX][newY] == 1) {
                                        return step;
                                    } else if (grid[newX][newY] == 0) {
                                        grid[newX][newY] = -1;
                                        isLand.offer(new int[]{newX, newY});
                                    }
                                }
                            }
                        }
                        ++step;
                    }
                }
            }
        }
        return 0;
    }



    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
        if (startGene.equals(endGene))
            return 0;
        if (!bankSet.contains(endGene)) {
            return -1;
        }

        Queue<String> queue = new LinkedList<>();
        queue.offer(startGene);
        bankSet.remove(startGene);
        int step = 1;
        char[] genes = new char[]{'A', 'C', 'G', 'T'};
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int k = 0; k < levelSize; k++) {
                String cur = queue.poll();
                for (int i = 0; i < cur.length(); i++) {
                    char x = cur.charAt(i);
                    for (char y : genes) {
                        if (x != y) {
                            StringBuilder sb = new StringBuilder(cur);
                            sb.setCharAt(i, y);
                            String next = sb.toString();
                            if (bankSet.contains(next)) {
                                if (next.equals(endGene))
                                    return step;
                                queue.offer(next);
                                bankSet.remove(next);
                            }
                        }
                    }
                }
            }
            ++step;
        }
        return -1;
    }


    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        class Inner {
            public Map<String, Integer> idMap = new HashMap<>();
            public List<List<Integer>> edges = new ArrayList<>();
            public Integer nodeNum = 0;

            public void addEdge(String edge) {
                addWord(edge);
                int id1 = idMap.get(edge);
                char[] array = edge.toCharArray();
                for (int i = 0; i < array.length; i++) {
                    char temp = array[i];
                    array[i] = '*';
                    String newWord = new String(array);
                    addWord(newWord);
                    int id2 = idMap.get(newWord);
                    this.edges.get(id1).add(id2);
                    this.edges.get(id2).add(id1);
                    array[i] = temp;
                }
            }

            private void addWord(String edge) {
                if (!idMap.containsKey(edge)) {
                    idMap.put(edge, this.nodeNum++);
                    edges.add(new ArrayList<>());
                }
            }
        }

        Inner inner = new Inner();
        for (String word : wordList) {
            inner.addEdge(word);
        }
        inner.addEdge(beginWord);
        if (!inner.idMap.containsKey(endWord)) {
            return 0;
        }

        int[] dis = new int[inner.nodeNum];
        Arrays.fill(dis, Integer.MAX_VALUE);
        int beginId = inner.idMap.get(beginWord), endId = inner.idMap.get(endWord);
        dis[beginId] = 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(beginId);
        while (!queue.isEmpty()) {
            int x = queue.poll();
            if (x == endId) {
                return dis[endId] / 2 + 1;
            }
            for (int it : inner.edges.get(x)) {
                if (dis[it] == Integer.MAX_VALUE) {
                    dis[it] = dis[x] + 1;
                    queue.offer(it);
                }
            }
        }

        return 0;
    }


    public boolean canReach(int[] arr, int start) {
        if (arr[start] == 0)
            return true;
        int length = arr.length;
        boolean[] visited = new boolean[length];
        Arrays.fill(visited, false);
        visited[start] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        while (!queue.isEmpty()) {
            int x = queue.poll();
            int tmp = x + arr[x];
            if (tmp < length && !visited[tmp]) {
                if (arr[tmp] == 0)
                    return true;
                queue.offer(tmp);
                visited[tmp] = true;
            }
            tmp = x - arr[x];
            if (tmp >= 0 && !visited[tmp]) {
                if (arr[tmp] == 0)
                    return true;
                queue.offer(tmp);
                visited[tmp] = true;
            }
        }
        return false;
    }


    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] dist = new int[m][n];
        // avoid dist[i][j] + 1 overflow.
        final int constant = Integer.MAX_VALUE - 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = (mat[i][j] == 1 ? constant : 0);
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int newI = i - 1, newJ = j - 1;
                if (newI >= 0)
                    dist[i][j] = Math.min(dist[i][j], dist[newI][j] + 1);
                if (newJ >= 0)
                    dist[i][j] = Math.min(dist[i][j], dist[i][newJ] + 1);
            }
        }

        // notice dist[i][i]'s calculation way
        for (int i = 0; i < m; i++) {
            for (int j = n - 1; j >= 0; j--) {
                int newI = i - 1, newJ = j + 1;
                if (newI >= 0)
                    dist[i][j] = Math.min(dist[i][j], dist[newI][j] + 1);
                if (newJ < n)
                    dist[i][j] = Math.min(dist[i][j], dist[i][newJ] + 1);
            }
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                int newI = i + 1, newJ = j - 1;
                if (newI < m)
                    dist[i][j] = Math.min(dist[i][j], dist[newI][j] + 1);
                if (newJ >= 0)
                    dist[i][j] = Math.min(dist[i][j], dist[i][newJ] + 1);
            }
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int newI = i + 1, newJ = j + 1;
                if (newI < m)
                    dist[i][j] = Math.min(dist[i][j], dist[newI][j] + 1);
                if (newJ < n)
                    dist[i][j] = Math.min(dist[i][j], dist[i][newJ] + 1);
            }
        }
        return dist;
    }


    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] == 1)
            return -1;
        int n = grid.length;
        int dist[][] = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        dist[0][0] = 1;

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        while (!queue.isEmpty()) {
            int[] front = queue.poll();
            int x = front[0], y = front[1];
            if (x == n - 1 && y == n - 1)
                return dist[x][y];
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    int newX = x + dx, newY = y + dy;
                    if (newX < 0 || newX >= n || newY < 0 || newY >= n)
                        continue;
                    if (grid[newX][newY] == 1 || dist[newX][newY] <= dist[x][y] + 1)
                        continue;
                    dist[newX][newY] = dist[x][y] + 1;
                    queue.offer(new int[]{newX, newY});
                }
            }
        }
        return -1;
    }


    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {

        class Inner {
            public Map<Integer, TreeNode> parents;
            public List<Integer> ans;
            public Integer k;

            public Inner(Integer k) {
                this.parents = new HashMap<>();
                this.ans = new ArrayList<>();
                this.k = k;
            }

            public void findParents(TreeNode root) {
                if (root.left != null) {
                    parents.put(root.left.val, root);
                    findParents(root.left);
                }
                if (root.right != null) {
                    parents.put(root.right.val, root);
                    findParents(root.right);
                }
            }

            public void findAns(TreeNode from, TreeNode node, Integer depth) {
                if (node == null)
                    return;
                if (depth == k) {
                    ans.add(node.val);
                    return;
                }
                if (node.left != from)
                    findAns(node, node.left, depth + 1);
                if (node.right != from)
                    findAns(node, node.right, depth + 1);
                if (parents.get(node.val) != from)
                    findAns(node, parents.get(node.val), depth + 1);
            }
        }
        Inner inner = new Inner(k);
        inner.findParents(root);
        inner.findAns(null, target, 0);
        return inner.ans;
    }


    public int shortestPathAllKeys(String[] grid) {
        int m = grid.length, n = grid[0].length();
        int sx = 0, sy = 0;
        Map<Character, Integer> key_to_idx = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c = grid[i].charAt(j);
                if (c == '@') {
                    sx = i;
                    sy = j;
                } else if (Character.isLowerCase(c)) {
                    if (!key_to_idx.containsKey(c)) {
                        int idx = key_to_idx.size();
                        key_to_idx.put(c, idx);
                    }
                }
            }
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sx, sy, 0});
        int keys = key_to_idx.size();
        int[][][] dist = new int[m][n][1 << keys];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(dist[i][j], -1);
            }
        }
        dist[sx][sy][0] = 0;

        int[][] directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!queue.isEmpty()) {
            int[] front = queue.poll();
            int x = front[0], y = front[1], mask = front[2];
            for (int[] direction : directions) {
                int newX = x + direction[0], newY = y + direction[1];
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX].charAt(newY) != '#') {
                    char ch = grid[newX].charAt(newY);
                    if (ch == '@' || ch == '.') {
                        if (dist[newX][newY][mask] == -1) {
                            dist[newX][newY][mask] = dist[x][y][mask] + 1;
                            queue.offer(new int[]{newX, newY, mask});
                        }
                    } else if (Character.isLowerCase(ch)) {
                        int idx = key_to_idx.get(ch);
                        int newMask = (mask | (1 << idx));
                        if (dist[newX][newY][newMask] == -1) {
                            dist[newX][newY][newMask] = dist[x][y][mask] + 1;
                            if (newMask == ((1 << keys) - 1)) {
                                return dist[newX][newY][newMask];
                            }
                            queue.offer(new int[]{newX, newY, newMask});
                        }
                    } else {
                        int idx = key_to_idx.get(Character.toLowerCase(ch));
                        int key = (mask & (1 << idx));
                        if (key != 0 && dist[newX][newY][mask] == -1) {
                            dist[newX][newY][mask] = dist[x][y][mask] + 1;
                            queue.offer(new int[]{newX, newY, mask});
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String[] grid = {"@.a..","###.#","b.A.B"};
        BreadthFirstSearchSolution solution = new BreadthFirstSearchSolution();
        System.out.println(solution.shortestPathAllKeys(grid));
    }
}
